package basic.courseLearn12.problem;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Stack;

//指标问题，指标：数组中累积和与最小值的乘积
public class IndicatorProblem {

    @Test
    public void test() {
        int[] nums = {3,1,2,5,4};
        Integer[] nexts = solution_1(nums);
        System.out.println();
        for(int i=0;i<nexts.length;i++){
            System.out.print(nexts[i]+" ");
        }
    }

    /**
     * 利用单调栈进行求解
     * @param nums 数组
     * @return 结果
     */
    public Integer[] solution_1(int[] nums) {
        //1. 定义栈，以及返回数组
        Integer[] nexts = new Integer[nums.length*2];
        Integer[] results = new Integer[nums.length];
        Stack<LinkedList<Integer>> stack = new Stack<LinkedList<Integer>>();
        //2. 循环
        for (int i = 0; i < nums.length; i++) {
            //2.1 栈空
            if (stack.isEmpty()) {
                LinkedList<Integer> tempList = new LinkedList<>();
                tempList.add(i);
                stack.push(tempList);
            }else { //2.2 栈非空
                //2.2.1 栈顶元素
                LinkedList<Integer> topList = stack.peek();
                int topIndex = topList.getLast();
                //2.2.2 判断
                if (nums[i] > nums[topIndex]) {
                    //入栈
                    LinkedList<Integer> tempList = new LinkedList<>();
                    tempList.add(i);
                    stack.push(tempList);
                }else if (nums[i] == nums[topIndex]){
                    //添加到栈顶元素之中
                    topList.add(i);
                    stack.pop();
                    stack.push(topList);
                }else {
                    //循环出栈，直到栈顶元素大于当前元素
                    while(!stack.isEmpty() && nums[i] < nums[stack.peek().getLast()]) {
                        LinkedList<Integer> tempList = stack.pop();
                        while(!tempList.isEmpty()) {
                            int index = tempList.removeLast();
                            Integer nextIndex = stack.isEmpty()? null : stack.peek().getLast();
                            nexts[index*2] = nextIndex;
                            nexts[index*2+1] = i;
                        }
                    }
                    //判断结束条件
                    if (stack.isEmpty()) {
                        //入栈
                        LinkedList<Integer> tempList = new LinkedList<>();
                        tempList.add(i);
                        stack.push(tempList);
                    }
                    if (nums[i] == nums[stack.peek().getLast()]) {
                        LinkedList<Integer> tempList = stack.peek();
                        tempList.add(i);
                        stack.pop();
                        stack.push(tempList);
                    }else {
                        LinkedList<Integer> tempList = new LinkedList<>();
                        tempList.add(i);
                        stack.push(tempList);
                    }
                }
            }
        }
        //3. 循环结束，栈中剩余元素出栈
        while(!stack.isEmpty()) {
            LinkedList<Integer> tempList = stack.pop();
            while(!tempList.isEmpty()) {
                int index = tempList.removeLast();
                Integer nextIndex = stack.isEmpty()? null : stack.peek().getLast();
                nexts[index*2] = nextIndex;
                nexts[index*2+1] = null;
            }
        }
        //4. 计算结果
        for (int i = 0; i < results.length; i++) {
            Integer a = nexts[i*2];
            Integer b = nexts[i*2+1];
            if (a == null && b != null) {       //4.1 左null,右非null
                results[i] = sum(nums, 0, b-1)*nums[i];
            }else if (a == null && b == null) {  //4.2 左null,右null
                results[i] = sum(nums, 0, nums.length-1)*nums[i];
            } else if (a != null && b == null) {  //4.3 左非null,右null
                results[i] = sum(nums, a+1, nums.length-1)*nums[i];
            } else {                              //4.4 左右都非null
                results[i] = sum(nums, a+1, b-1)*nums[i];
            }
        }
        for(int i=0;i<nexts.length;i++){
            System.out.print(nexts[i]+" ");
        }
        return results;
    }

    //计算(a,b)的和
    public int sum(int[] nums, int a, int b) {

        int sum = 0;
        for (int i = a; i <= b; i++) {
            sum += nums[i];
        }
        return sum;
    }




}
